From 357b221679ed61aeb1d34a4ef057c0315e71633a Mon Sep 17 00:00:00 2001 From: Sven Neumann Date: Sat, 22 Mar 2008 22:09:19 +0000 Subject: [PATCH] Applied patch from Jan Heller that introduces list and hash table 2008-03-22 Sven Neumann Applied patch from Jan Heller that introduces list and hash table functionality and changes the babl database to use coalesced hashing (bug #523507): * babl/Makefile.am * babl/babl-list.[ch] * babl/babl-hash-table.[ch]: new files providing list and hash table functionality. * babl/babl-internal.h: include the new header files. * babl/babl-db.[ch]: use the new code. * babl/babl-fish.c: changed accordingly. svn path=/trunk/; revision=294 --- ChangeLog | 17 ++++ babl/Makefile.am | 8 +- babl/babl-db.c | 208 +++++++++++++------------------------- babl/babl-db.h | 62 ++++++++---- babl/babl-fish.c | 4 +- babl/babl-hash-table.c | 223 +++++++++++++++++++++++++++++++++++++++++ babl/babl-hash-table.h | 71 +++++++++++++ babl/babl-internal.h | 13 +-- babl/babl-list.c | 106 ++++++++++++++++++++ babl/babl-list.h | 56 +++++++++++ 10 files changed, 602 insertions(+), 166 deletions(-) create mode 100644 babl/babl-hash-table.c create mode 100644 babl/babl-hash-table.h create mode 100644 babl/babl-list.c create mode 100644 babl/babl-list.h diff --git a/ChangeLog b/ChangeLog index 0c33ded..23fa24d 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,20 @@ +2008-03-22 Sven Neumann + + Applied patch from Jan Heller that introduces list and hash table + functionality and changes the babl database to use coalesced + hashing (bug #523507): + + * babl/Makefile.am + * babl/babl-list.[ch] + * babl/babl-hash-table.[ch]: new files providing list and hash + table functionality. + + * babl/babl-internal.h: include the new header files. + + * babl/babl-db.[ch]: use the new code. + + * babl/babl-fish.c: changed accordingly. + 2008-03-16 Mukund Sivaraman * babl/babl-extension.c: getenv() can return NULL. diff --git a/babl/Makefile.am b/babl/Makefile.am index 41c3602..b1038b8 100644 --- a/babl/Makefile.am +++ b/babl/Makefile.am @@ -27,7 +27,9 @@ c_sources = \ babl-sampling.c \ babl-sanity.c \ babl-type.c \ - babl-util.c + babl-util.c \ + babl-list.c \ + babl-hash-table.c h_sources = \ babl-classes.h \ @@ -36,7 +38,9 @@ h_sources = \ babl-internal.h \ babl-memory.h \ babl-util.h \ - babl.h + babl.h \ + babl-list.h \ + babl-hash-table.h library_includedir=$(includedir)/babl-$(BABL_API_VERSION)/babl library_include_HEADERS = \ diff --git a/babl/babl-db.c b/babl/babl-db.c index 266f8d5..735bdbc 100644 --- a/babl/babl-db.c +++ b/babl/babl-db.c @@ -16,111 +16,100 @@ * . */ +/* Reimplementation of database code using redundant hash tables + * for faster searching by id/name and using list for fast item enumeration. + * Copyright (C) 2008, Jan Heller + */ + #define _BABL_DB_C #include #include "babl-internal.h" -#define DB_INITIAL_SIZE 16 -#define DB_INCREMENT_SIZE 16 - -static inline int hash (const char *str) +static int +db_find_by_name (Babl *item, void *data) { - int ret = 0; - int i = 1; - - while (*str) - ret = (ret + (i++ * (*str++ & 31))) % (HASH_TABLE_SIZE - 1); - return ret; + if (!strcmp (item->instance.name, (char *) data)) + return 1; + return 0; } - -Babl * -babl_db_find (BablDb *db, - const char *name) +static int +db_find_by_id (Babl *item, void *data) { - Babl *ret = babl_db_exist (db, 0, name); - - if (!ret) - { - const char *sample_type = "unknwon"; + if (item->instance.id == *((int *) data)) + return 1; + return 0; +} - if (db->items[0]) - sample_type = babl_class_name (db->items[0]->class_type); - babl_log ("failed (query performed on a %s database)", sample_type); - } - return ret; +static int +db_hash_by_name (BablHashTable *htab, Babl *item) +{ + return babl_hash_by_str (htab, item->instance.name); } +static int +db_hash_by_id (BablHashTable *htab, Babl *item) +{ + return babl_hash_by_int (htab, item->instance.id); +} BablDb * babl_db_init (void) { BablDb *db = babl_calloc (sizeof (BablDb), 1); - db->size = DB_INITIAL_SIZE; - db->count = 0; - db->items = NULL; - if (db->size) - { - db->items = babl_calloc (sizeof (BablInstance *), db->size); - } - return db; -} - + db->name_hash = babl_hash_table_init (db_hash_by_name, db_find_by_name); + db->id_hash = babl_hash_table_init (db_hash_by_id, db_find_by_id); + db->babl_list = babl_list_init (); -int -babl_db_count (BablDb *db) -{ - return db->count; + return db; } void babl_db_destroy (BablDb *db) { - babl_free (db->items); + babl_assert (db); + + babl_hash_table_destroy (db->name_hash); + babl_hash_table_destroy (db->id_hash); + babl_list_destroy (db->babl_list); babl_free (db); } Babl * -babl_db_insert (BablDb *db, - Babl *item) +babl_db_find (BablDb *db, + const char *name) { - Babl *collision; - - babl_assert (db && item); - babl_assert (item->instance.name); - - collision = babl_db_exist (db, item->instance.id, item->instance.name); - - if (collision) - return collision; + return babl_hash_table_find (db->name_hash, babl_hash_by_str (db->name_hash, name), (void *) name); +} - if (db->count + 1 > db->size) /* must reallocate storage */ - { - Babl **new_items; +int +babl_db_count (BablDb *db) +{ + return db->babl_list->count; +} - new_items = babl_realloc (db->items, (db->size + DB_INCREMENT_SIZE) * sizeof (BablInstance *)); - babl_assert (new_items); +Babl * +babl_db_insert (BablDb *db, + Babl *item) +{ - db->items = new_items; + Babl *found = babl_db_exist (db, item->instance.id, item->instance.name); - /* null out the currently unused portions of memory */ - memset (db->items + db->size, 0, DB_INCREMENT_SIZE * sizeof (Babl *)); - db->size += DB_INCREMENT_SIZE; - } + if (found) + return found; - { - int key = hash (item->instance.name); - if (db->hash[key] == NULL) - db->hash[key] = item; - } - db->items[db->count++] = item; + if (item->instance.id) + babl_hash_table_insert (db->id_hash, item); + babl_hash_table_insert (db->name_hash, item); + babl_list_insert (db->babl_list, item); /* this point all registered items pass through, a nice * place to brand them with where the item came from. */ item->instance.creator = babl_extender (); return item; + } void @@ -128,84 +117,31 @@ babl_db_each (BablDb *db, BablEachFunction each_fun, void *user_data) { - int i; - - for (i = 0; i < db->count; i++) - { - if (db->items[i]) - { - if (each_fun ((Babl *) db->items[i], user_data)) - break; - } - } + babl_list_each_temp (db->babl_list, each_fun, user_data); } -static inline void -babl_db_each_inline (BablDb *db, - BablEachFunction each_fun, - void *user_data) -{ - int i; - - for (i = 0; i < db->count; i++) - { - if (db->items[i]) - { - if (each_fun ((Babl *) db->items[i], user_data)) - break; - } - } -} -typedef struct BablDbExistData +Babl * +babl_db_exist (BablDb *db, + int id, + const char *name) { - int id; - const char *name; - Babl *ret; -} BablDbExistData; + if (id) + return babl_hash_table_find (db->id_hash, babl_hash_by_int (db->id_hash, id), &id); + return babl_hash_table_find (db->name_hash, babl_hash_by_str (db->name_hash, name), (void *) name); +} -static int -babl_db_each_exist (Babl *babl, - void *void_data) +Babl * +babl_db_exist_by_id (BablDb *db, + int id) { - BablDbExistData *data = void_data; - - if (data->id && data->id == babl->instance.id) - { - data->ret = babl; - return 1; /* stop iterating */ - } - else if (data->name && !strcmp (babl->instance.name, data->name)) - { - data->ret = babl; - return 1; /* stop iterating */ - } - return 0; /* continue iterating */ + return babl_hash_table_find (db->id_hash, babl_hash_by_int (db->id_hash, id), &id); } Babl * -babl_db_exist (BablDb *db, - int id, - const char *name) +babl_db_exist_by_name (BablDb *db, + const char *name) { - Babl *ret = NULL; - - if (name) - ret = db->hash[hash (name)]; - if (ret && - name[0] == ret->instance.name[0] && - !strcmp (name, ret->instance.name)) - return ret; - - { - BablDbExistData data; - - data.id = id; - data.name = name; - data.ret = NULL; - - babl_db_each_inline (db, babl_db_each_exist, &data); - - return data.ret; - } + return babl_hash_table_find (db->name_hash, babl_hash_by_str (db->name_hash, name), (void *) name); } + diff --git a/babl/babl-db.h b/babl/babl-db.h index 9c49a3d..1eb3700 100644 --- a/babl/babl-db.h +++ b/babl/babl-db.h @@ -19,33 +19,55 @@ #ifndef _DB_H #define _DB_H -#ifndef _BABL_INTERNAL_H -#error babl-db.h is only to be included after babl-internal.h +#ifndef _BABL_CLASSES_H +#error babl-db.h is only to be included after babl-classes.h #endif +#include "babl-list.h" +#include "babl-hash-table.h" + typedef struct _BablDb BablDb; -#define HASH_TABLE_SIZE 128 typedef struct _BablDb { - Babl *hash [HASH_TABLE_SIZE]; - int size; - int count; - Babl **items; + BablHashTable *name_hash; + BablHashTable *id_hash; + BablList *babl_list; } _BablDb; -BablDb * babl_db_init (void); -void babl_db_destroy (BablDb *db); -void babl_db_each (BablDb *db, - BablEachFunction each_fun, - void *user_data); -int babl_db_count (BablDb *db); -Babl * babl_db_insert (BablDb *db, - Babl *entry); -Babl * babl_db_exist (BablDb *db, - int id, - const char *name); -Babl * babl_db_find (BablDb *db, - const char *name); + +BablDb * +babl_db_init (void); + +void +babl_db_destroy (BablDb *db); + +void +babl_db_each (BablDb *db, + BablEachFunction each_fun, + void *user_data); + +int +babl_db_count (BablDb *db); + +Babl * +babl_db_insert (BablDb *db, + Babl *entry); + +Babl * +babl_db_exist (BablDb *db, + int id, + const char *name); + +Babl * +babl_db_exist_by_name (BablDb *db, + const char *name); +Babl * +babl_db_exist_by_id (BablDb *db, + int id); + +Babl * +babl_db_find (BablDb *db, + const char *name); #endif diff --git a/babl/babl-fish.c b/babl/babl-fish.c index d0c148f..fc8d7e3 100644 --- a/babl/babl-fish.c +++ b/babl/babl-fish.c @@ -62,9 +62,9 @@ go_fishing (const Babl *source, BablDb *db = babl_fish_db (); int i; - for (i=0; icount; i++) + for (i = 0; i < db->babl_list->count; i++) { - Babl *item = db->items[i]; + Babl *item = db->babl_list->items[i]; if ((void *) source == (void *) item->fish.source && (void *) destination == (void *) item->fish.destination && (item->class_type == BABL_FISH_PATH || /* accept only paths */ diff --git a/babl/babl-hash-table.c b/babl/babl-hash-table.c new file mode 100644 index 0000000..b88faa2 --- /dev/null +++ b/babl/babl-hash-table.c @@ -0,0 +1,223 @@ +/* babl - dynamically extendable universal pixel conversion library. + * Copyright (C) 2005, Øyvind Kolås. + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General + * Public License along with this library; if not, see + * . + */ + +/* Implementation of hash table data structure based on coalesced hashing. + * Copyright (C) 2008, Jan Heller + */ + +#include "babl-internal.h" + +#define BABL_HASH_TABLE_INITIAL_MASK 0x7F + +/* static functions declarations */ +static inline int +hash_insert (BablHashTable *htab, + Babl *item); + +static void +hash_rehash (BablHashTable *htab); + + +inline int +babl_hash_by_str (BablHashTable *htab, + const char *str) +{ + int hash = 0; + + while (*str) + { + hash += *str++; + hash += (hash << 10); + hash ^= (hash >> 6); + } + hash += (hash << 3); + hash ^= (hash >> 11); + hash += (hash << 15); + + return (hash & htab->mask); +} + +inline int +babl_hash_by_int (BablHashTable *htab, + int id) +{ + int hash = 0; + int i; + + for (i = 0; i < sizeof (int); i++) + { + hash += id & 0xFF; + hash += (hash << 10); + hash ^= (hash >> 6); + id >>= 8; + } + hash += (hash << 3); + hash ^= (hash >> 11); + hash += (hash << 15); + + return (hash & htab->mask); +} + +static inline int +hash_insert (BablHashTable *htab, + Babl *item) +{ + int hash = htab->hash_func(htab, item); + + if (htab->data_table[hash] == NULL) + { + /* create new chain */ + htab->data_table[hash] = item; + } + else + { + int it, oit, cursor = 0; + + while ((cursor < (htab->mask + 1)) && (htab->data_table[cursor] != NULL)) + ++cursor; + + htab->data_table[cursor] = item; + + for (oit = hash, it = htab->chain_table[oit]; it != -1; oit = it, it = htab->chain_table[oit]) + ; + htab->chain_table[oit] = cursor; + } + + htab->count++; + return 0; +} + +static void +hash_rehash (BablHashTable *htab) +{ + Babl *item; + int i; + BablHashTable *nhtab = babl_calloc (sizeof (BablHashTable), 1); + + nhtab->data_table = NULL; + nhtab->chain_table = NULL; + nhtab->mask = (htab->mask << 1) + 1; + nhtab->count = 0; + nhtab->hash_func = htab->hash_func; + nhtab->find_func = htab->find_func; + if (nhtab->mask) + { + nhtab->data_table = babl_calloc (sizeof (BablInstance *), babl_hash_table_size(nhtab)); + nhtab->chain_table = babl_malloc (sizeof (int *) * babl_hash_table_size(nhtab)); + memset (nhtab->chain_table, -1, sizeof (int) * babl_hash_table_size(nhtab)); + } + + for (i = 0; i < babl_hash_table_size (htab); i++) + { + item = htab->data_table[i]; + babl_hash_table_insert (nhtab, item); + } + + htab->mask = nhtab->mask; + babl_free (htab->data_table); + babl_free (htab->chain_table); + htab->data_table = nhtab->data_table; + htab->chain_table = nhtab->chain_table; + babl_free (nhtab); +} + +inline int +babl_hash_table_size (BablHashTable *htab) +{ + return htab->mask + 1; +} + +BablHashTable * +babl_hash_table_init (BablHashValFunction hfunc, + BablHashFindFunction ffunc) +{ + BablHashTable *htab; + + babl_assert(hfunc); + babl_assert(ffunc); + + htab = babl_calloc (sizeof (BablHashTable), 1); + babl_assert (htab); + + htab->data_table = NULL; + htab->chain_table = NULL; + htab->mask = BABL_HASH_TABLE_INITIAL_MASK; + htab->count = 0; + htab->hash_func = hfunc; + htab->find_func = ffunc; + if (htab->mask) + { + htab->data_table = babl_calloc (sizeof (BablInstance *), babl_hash_table_size(htab)); + htab->chain_table = babl_malloc (sizeof (int *) * babl_hash_table_size(htab)); + memset (htab->chain_table, -1, sizeof (int) * babl_hash_table_size(htab)); + } + + return htab; +} + +void +babl_hash_table_destroy (BablHashTable *htab) +{ + babl_assert (htab); + + babl_free (htab->data_table); + babl_free (htab->chain_table); + babl_free (htab); +} + +int +babl_hash_table_insert (BablHashTable *htab, + Babl *item) +{ + babl_assert (htab); + babl_assert (BABL_IS_BABL(item)); + + if (babl_hash_table_size (htab) < htab->count + 1) + hash_rehash (htab); + return hash_insert (htab, item); +} + +Babl * +babl_hash_table_find (BablHashTable *htab, + int hash, + void *data) +{ + int it; + Babl *item; + + babl_assert (htab); + + it = hash; + item = htab->data_table[it]; + + if (!item) + return NULL; + + for (;;) + { + if (htab->find_func (item, data)) + return item; + it = htab->chain_table[it]; + if (it == -1) + break; + item = htab->data_table[it]; + } + + return NULL; +} + diff --git a/babl/babl-hash-table.h b/babl/babl-hash-table.h new file mode 100644 index 0000000..00cc395 --- /dev/null +++ b/babl/babl-hash-table.h @@ -0,0 +1,71 @@ +/* babl - dynamically extendable universal pixel conversion library. + * Copyright (C) 2005, Øyvind Kolås. + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General + * Public License along with this library; if not, see + * . + */ + +#ifndef _BABL_HASH_TABLE_H +#define _BABL_HASH_TABLE_H + +#ifndef _BABL_CLASSES_H +#error babl-hash-table.h is only to be included after babl-classes.h +#endif + + +typedef struct _BablHashTable BablHashTable; + +typedef int (*BablHashValFunction) (BablHashTable *htab, Babl *item); +typedef int (*BablHashFindFunction) (Babl *item, void *data); + +typedef struct _BablHashTable +{ + Babl **data_table; + int *chain_table; + int mask; + int count; + BablHashValFunction hash_func; + BablHashFindFunction find_func; +} _BablHashTable; + + +BablHashTable * +babl_hash_table_init (BablHashValFunction hfunc, + BablHashFindFunction ffunc); + +inline int +babl_hash_by_str (BablHashTable *htab, + const char *str); + +inline int +babl_hash_by_int (BablHashTable *htab, + int id); + +inline int +babl_hash_table_size (BablHashTable *htab); + +int +babl_hash_table_insert (BablHashTable *htab, + Babl *item); + +Babl * +babl_hash_table_find (BablHashTable *htab, + int hash, + void *data); + +void +babl_hash_table_destroy (BablHashTable *htab); + + +#endif diff --git a/babl/babl-internal.h b/babl/babl-internal.h index 9afac6f..12e19df 100644 --- a/babl/babl-internal.h +++ b/babl/babl-internal.h @@ -37,7 +37,8 @@ #include "babl.h" #define _BABL_INTERNAL_H - +#include "babl-list.h" +#include "babl-hash-table.h" #include "babl-db.h" #include "babl-ids.h" #include "babl-util.h" @@ -190,10 +191,10 @@ Babl * \ babl_##type_name##_id (int id) \ { \ Babl *babl; \ - babl = babl_db_exist (db, id, NULL); \ + babl = babl_db_exist_by_id (db, id); \ if (!babl) \ { \ - babl_fatal ("%s(%i): not found", __func__, id); \ + babl_fatal ("%s(%i): not found", __func__, id); \ } \ return babl; \ } @@ -206,13 +207,13 @@ babl_##type_name (const char *name) \ \ if (babl_hmpf_on_name_lookups) \ { \ - babl_log ("%s(\"%s\"): hmpf!", __func__, name); \ + babl_log ("%s(\"%s\"): hmpf!", __func__, name); \ } \ - babl = babl_db_exist (db, 0, name); \ + babl = babl_db_exist_by_name (db, name); \ \ if (!babl) \ { \ - babl_fatal ("%s(\"%s\"): not found", __func__, name); \ + babl_fatal ("%s(\"%s\"): not found", __func__, name); \ } \ return babl; \ } diff --git a/babl/babl-list.c b/babl/babl-list.c new file mode 100644 index 0000000..e67a5c8 --- /dev/null +++ b/babl/babl-list.c @@ -0,0 +1,106 @@ +/* babl - dynamically extendable universal pixel conversion library. + * Copyright (C) 2005, Øyvind Kolås. + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General + * Public License along with this library; if not, see + * . + */ + +/* Implementation of list data structure. This is a bit superior + * to the list implementation in babl-util.c. + * Copyright (C) 2008, Jan Heller + * + * TODO: migrate babl to BablList + */ + +#include "babl-internal.h" + +#define BABL_LIST_INITIAL_SIZE 0x7F + +BablList * +babl_list_init (void) +{ + BablList *list = babl_calloc (sizeof (BablList), 1); + + babl_assert (list); + + list->size = BABL_LIST_INITIAL_SIZE; + list->count = 0; + list->items = NULL; + if (list->size) + { + list->items = babl_calloc (sizeof (BablInstance *), list->size); + } + + return list; +} + +void +babl_list_destroy (BablList *list) +{ + babl_assert (list); + + babl_free (list->items); + babl_free (list); +} + +int +babl_list_size (BablList *list) +{ + babl_assert (list); + return list->count; +} + +void +babl_list_insert (BablList *list, + Babl *item) +{ + babl_assert(list); + babl_assert(BABL_IS_BABL(item)); + + if (list->size < list->count + 1) + { + Babl **new_items; + + new_items = babl_realloc (list->items, (list->size * 2) * sizeof (BablInstance *)); + babl_assert (new_items); + list->items = new_items; + memset (list->items + list->size, 0, list->size * sizeof (BablInstance *)); + list->size *= 2; + } + list->items[list->count++] = item; +} + +/* TODO: Rename babl_list_each_temp to babl_list_each after the list migration + */ + +void +babl_list_each_temp (BablList *list, + BablEachFunction each_fun, + void *user_data) +{ + int i; + + babl_assert(list); + babl_assert(each_fun); + + for (i = 0; i < list->count; i++) + { + if (list->items[i]) + { + if (each_fun ((Babl *) list->items[i], user_data)) + break; + } + } +} + diff --git a/babl/babl-list.h b/babl/babl-list.h new file mode 100644 index 0000000..af05fe8 --- /dev/null +++ b/babl/babl-list.h @@ -0,0 +1,56 @@ +/* babl - dynamically extendable universal pixel conversion library. + * Copyright (C) 2005, Øyvind Kolås. + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General + * Public License along with this library; if not, see + * . + */ + +#ifndef _BABL_LIST_H +#define _BABL_LIST_H + +#ifndef _BABL_CLASSES_H +#error babl-list.h is only to be included after babl-classes.h +#endif + + +typedef struct _BablList BablList; + +typedef struct _BablList +{ + int count; + int size; + Babl **items; +} _BablList; + + +BablList * +babl_list_init (void); + +void +babl_list_destroy (BablList *list); + +int +babl_list_size (BablList *list); + +void +babl_list_insert (BablList *list, + Babl *item); + +void +babl_list_each_temp (BablList *list, + BablEachFunction each_fun, + void *user_data); + + +#endif -- 2.30.2